"""
@author:HY
@time:2020/12/3:19:15
"""
import numpy as np
import sys

class KM_Algorithm_1:
    """
    此类是一个对KM算法的成功实现。
    本需求中不可直接使用，因为订单与车辆之间可能不能匹配的边以及订单会匹配失败的可能性
    """

    def __init__(self, Bipartite_Graph):
        self.Bipartite_Graph = Bipartite_Graph


        # 左右结点数量记录  
        self.left = self.Bipartite_Graph.shape[0]  # 以左边为主
        self.right = self.Bipartite_Graph.shape[1]

        # 初始化顶标
        self.label_left = np.max(self.Bipartite_Graph, axis=1)  # 设置左边顶标为权重最大值（每行的最大值）
        self.label_right = np.zeros(self.right)  # 右边集合的顶标设置为0

        # 初始化辅助变量——是否已匹配
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)

        # 初始化右边的匹配结果.如果已匹配就会对应匹配结果
        self.match_right = np.empty(self.left) * np.nan

        # 用inc记录需要减去的权值d，不断取最小值故初始化为较大值。
        self.inc = 9999

    def match(self, boy):
        boy = int(boy)
        # 记录下这个boy已经被寻找
        self.visit_left[boy] = True
        for girl in range(self.right):
            # 如果这个女生还没匹配
            if not self.visit_right[girl]:
                gap = self.label_left[boy] + self.label_right[girl] - self.Bipartite_Graph[boy][girl]
                if gap == 0:   # # 差值为0，是可行的替换。所以可以直接尝试替换。后面不行再说。这个列表是记录希望匹配的
                    self.visit_right[girl] = True

                    # 女生未被匹配，或虽然已被匹配，但是已匹配对象(男生)有其他可选备胎
                    if np.isnan(self.match_right[girl]) or self.match(self.match_right[girl]):
                        self.match_right[girl] = boy
                        # 递归匹配，匹配成功
                        return 1

                # 找到权值最小的差距
                elif self.inc > gap:
                    self.inc = gap
        return 0

    def Kuh_Munkras(self):

        self.match_right = np.empty(self.left) * np.nan

        # find the perfect match
        for man in range(self.left):
            while True:
                self.inc = 9999  # 初始化最小距离为一个很大的值
                self.reset()  # 每次寻找过的路径，所有要重置一下

                # 可找到可行匹配
                if self.match(man):
                    break

                # 不能找到可行匹配
                # (1)将所有在增广路中的boy方点的label全部减去最小常数
                # (2)将所有在增广路中的girl方点的label全部加上最小常数
                for k in range(self.left):
                    if self.visit_left[k]:
                        self.label_left[k] -= self.inc
                for n in range(self.right):
                    if self.visit_right[n]:
                        self.label_right[n] += self.inc

    def calculateSum(self):
        sum = 0
        for i in range(self.left):
            sum += self.Bipartite_Graph[int(self.match_right[i])][i]
        return sum

    def getResult(self):
        return self.match_right


    def reset(self):
        # variable for record path
        self.visit_left = np.zeros(self.left, dtype=bool)
        self.visit_right = np.zeros(self.right, dtype=bool)


def change_cost(matrix):
    """
    与上面的类搭配使用计算成本
    :param matrix:
    :return:
    """

    cost_matrix = []
    for row in matrix:
        cost_row = []
        for col in row:
            cost_row += [- col]
        cost_matrix += [cost_row]

    km = KM_Algorithm_1(Bipartite_Graph=np.array(cost_matrix))

    km.Kuh_Munkras()
    km.Bipartite_Graph = - km.Bipartite_Graph

    print('最小权值:')
    print(km.Bipartite_Graph)
    print(km.calculateSum())


def test1():
    """
    测试最大匹配
    :return:
    """
    n = input("输入行列数n:")  # 输入二维数组的行数和列数
    if n == '':
        print("使用默认矩阵启动")
        graph = [[5, 9, 1,100,1,1,1], [10, 3, 2,5,1,1,1], [8, 7, 4,3,1,1,1], [8, 7, 4,3,1,1,1],
        [5, 9, 1,100,1,1,1], [5, 9, 1,100,1,1,1], [5, 9, 1,100,1,1,1],]
        km = KM_Algorithm_1(Bipartite_Graph=np.array(graph))
    else:
        n = int(n)
        graph = [[0] * n] * n  # 初始化二维数组
        print("输入一个n*n的二维数组，同一行的数字使用空格分隔，不同行的数字用回车换行:")
        for i in range(n):
            graph[i] = input().split(" ")
            graph[i] = [int(j) for j in graph[i]]
        print(graph)  # 打印二维数组
        km = KM_Algorithm_1(Bipartite_Graph=np.array(graph))


    km.Kuh_Munkras()
    print('最大权值:')
    print(km.Bipartite_Graph)
    print(km.calculateSum())


def test2():
    """
    测试最小匹配
    :return:
    """
    # graph = [[5, 9, 1], [10, 3, 2], [8, 7, 4]]
    graph = [[4, 0, 0], [3, 0, 0], [0, 0, 2]]
    # graph = [[1, 2, 1000000, 1000000, 1000000], 
    #          [1, 1, 1000000, 1000000, 1000000], 
    #          [3, 3, 1000000, 1000000, 1000000], 
    #          [5, 0, 1000000, 1000000, 1000000]]
    change_cost(graph)


if __name__ == '__main__':
    # test1()
    test1()
